// *****************************************************************************
// Filename:    rotated_find.cc
// Date:        2012-07-17 12:38
// Author:      Guangda Lai
// Email:       lambda2fei@gmail.com
// Description: TODO(laigd): Put the file description here.
// *****************************************************************************

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::ifstream;
using std::map;
using std::ofstream;
using std::set;
using std::string;
using std::vector;

// Assuming that *__last < *__first. Returns the first iterator res where
// *res >= __val.
template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter InnerRotatedFind(_ForwardIter __first,
                              _ForwardIter __last,
                              const _Tp& __val,
                              _Distance*) {
  _Distance __len = 0;
  distance(__first, __last, __len);
  _Distance __half;
  _ForwardIter __middle;

  while (__len > 0) {
    __half = __len >> 1;
    __middle = __first;
    advance(__middle, __half);

    if (*__middle < __val && __val < *__first ||
        !(__val < *__first) && !(*__middle < __val)) {
      __len = __half;
    } else {
      // __val <= *__middle < *__first || *__middle < *__first <= __val
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
  }
  return __first;
}

// Returns the first iterator res where *res >= __val in [__first, __last). Here
// 'the first' means the same in lower_bound when the [__first, __last) is
// sorted but not rotated.
// If all the element are same, returns __first or __last, according to __val.
template <class _ForwardIter, class _Tp>
inline _ForwardIter RotatedFind(_ForwardIter __first,
                                _ForwardIter __last,
                                const _Tp& __val) {
  typedef __STD::distance_type(__first) _Distance;
  _Distance __len = 0;
  distance(__first, __last, __len);
  __len = __len - 1;

  _ForwardIter __first_bak, __last_but_one;
  __first_bak = __first;
  __last_but_one = __first;
  advance(__last_but_one, __len - 1);

  while (!(*__last_but_one < *__first) && __len > 0) {
    // i.e. *__first == *__last_but_one.
    ++__first;
    __len = __len - 1;
  }
  if (__len == 0) {
    return (!(*__first_bak < __val) ? __first_bak : __last);
  }
  return InnerRotatedFind(__first, __last, __val, _Distance);
}

#define CHECK_EQ(a, b) \
    if ((a) != (b)) { \
      cerr << "Error!" << endl; \
      exit(1); \
    }

void Test() {
  int t1[] = { 1, 1, 1, 1, 1, };
  CHECK_EQ(RotatedFind(t1, t1 + 5, 1), t1);

  int t2[] = { 2, 1, 1, 1, 1, };
  int t3[] = { 1, 1, 2, 1, 1, };
  int t4[] = { 1, 1, 1, 1, 2, };
  int t5[] = { 2, 2, 2, 1, 1, };
  int t6[] = { 3, 4, 5, 1, 2, };
  int t6[] = { 1, 2, 3, 4, 5, };
}

int main(int argc, char **argv) {
  return 0;
}
